hill climbing with backtracking

Simple forgetful hill climbing constantly tries to look for neighbouring places or states that are better than the current state, but keeps no track of where it has been. By adding backtracking hill climbing can deal with impasses, when it cannot find suitable next states, or with local maxima by restarting from a previous state. If the hill-climbing is deterministic (choosing the very best next step) the algorithm also has to keep track of what choices it made in the past otherwise it would simply repeat the same steps after backtracking! This is less important for stochasitic variants of hill climbing (such as simulated annealing).